Factoring Matrices

May 2023

Singular Value Decomposition (SVD)

Let $A$ be an $m \times n$ matrix. The Singular Value Decomposition (SVD) is

A = U \Sigma V^T

Where:

Let

A = \begin{bmatrix} 5 & 5 \\ -1 & 7 \end{bmatrix}

Compute $V$ :

A^TA = \begin{bmatrix} 26 & 18 \\ 18 & 74 \end{bmatrix}, \quad \lambda = 20, 80

Unit eigenvectors:

V_1 = \frac{1}{\sqrt{10}} \begin{bmatrix}-3 \\ 1\end{bmatrix}, \quad V_2 = \frac{1}{\sqrt{10}} \begin{bmatrix}1 \\ 3\end{bmatrix}

Combine into

V = \frac{1}{\sqrt{10}} \begin{bmatrix}-3 & 1 \\ 1 & 3\end{bmatrix}, \quad \Sigma = \begin{bmatrix} 2\sqrt{5} & 0 \\ 0 & 4\sqrt{5} \end{bmatrix}

Then $U$ satisfies $AV = U\Sigma$ :

U = \frac{1}{\sqrt{2}} \begin{bmatrix}1 & 1 \\ -1 & 1\end{bmatrix}

For a $m \times n$ linearly independent matrix $A$ :

A = QR

Compute $Q$ via Gram-Schmidt:

n_k = v_k - \sum_{i=1}^{k-1} \frac{v_k \cdot n_i}{\|n_i\|^2} n_i, \quad q_k = \frac{n_k}{\|n_k\|}

Example:

A = \begin{bmatrix} 2 & 3 \\ 2 & 4 \\ 1 & 1 \end{bmatrix}, \quad Q = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ 2 & 2 \\ 1 & -2 \end{bmatrix}, \quad R = \begin{bmatrix}3 & 5 \\ 0 & 1\end{bmatrix}

For square $A$ :

A = LU

For symmetric positive definite $A$ :

A = LL^T

Entries of $L$ :

L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}, \quad L_{ij} = \frac{1}{L_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right), \ i>j